package com.data.construct.binaryTree;

import java.util.ArrayList;
import java.util.List;

/**
 * 寻找所有路径的方法
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/11/12 0012 10:33
 * @Modified By:
 */
public class FindAllPath {

    /**
     * 递归遍历寻寻找所有路径
     * 这种情况下递归的方式更常用
     *
     * @param root
     * @return
     */
    public List<List<Integer>> findAllPathOfDFS(TreeNode root) {
        if (root == null) {
            return null;
        }
        // res 用来存放所有路径
        List<List<Integer>> res = new ArrayList<>();
        // path 用来存放当前正在遍历的路径
        List<Integer> path = new ArrayList<>();

        // 从根节点开始 DFS 遍历
        traverse(root, path, res);
        return res;
    }

    private void traverse(TreeNode root, List<Integer> path, List<List<Integer>> res) {
        if (root == null) {
            return;
        }

        // 前序位置进入节点时，把节点值加入 path
        path.add(root.val);

        if (root.left == null && root.right == null) {
            // 到达叶子节点，找到一条路径
            res.add(path);
        }
        // 递归左子节点
        traverse(root.left, path, res);

        // 中序位置, 递归右子节点
        traverse(root.right, path, res);

        // 后序位置离开节点时，把节点值从 path 中移除
        path.remove(root.val);
    }
}
